동적 프로그래밍(비교)

r23 vs r24
... ...
10 10
> Divide & Conquer, Overlapping Subproblem
11 11
12 12
=== 최적제어에서의 동적 프로그래밍 ===
13
기본적으로 동적 프로그래밍은 최적 제어 문제를 해결하기 위해서 고안된 방법이다. 특히나 이산 시간(discrete time) 제어 문제에 적용하기 위한 방법으로 시작한다.
14
13
기본적으로 동적 프로그래밍은 최적 제어 문제를 해결하기 위해서 고안된 방법이다. 특히나 이산 시간(discrete time) 제어 문제에 적용하기 위한 방법으로 시작한다. 최적제어는 어떤 시스템의 상태 [math(x(t))]와 현재의 입력[math(u(t))]을 기반으로 계산되는 비용 [math(J(t))]을 최소화 하는 문제상황을 말한다. 벨만은 이 문제를 해결하기 위해서 2가지의 핵심 개념을 제시하는데 첫번째는 '''최적성의 원리'''이다. 최적성의 원리란 별로 어렵지 않다. 어떤 문제에 대한 최적의 경로(=비용을 최소화 하는)가 존재할때, 그 하위 경로 역시 최적이어야 한다라는 의미이다.
15 14
=== 컴퓨터 과학에서의 동적 프로그래밍 ===
16 15
상태기반의 문제를 재귀적으로 해석하는 방법은 너무나도 일반화 하기 쉬운 강력한 방법이었다. 이 문제를 최적제어 문제에만 쓰기 아까웠던 벨만은 다른 문제에도 사용하기 시작하였고 최적 경로, 그래프 탐색 문제등을 시작으로 동적 프로그래밍의 사상 아래에서 해결될 수 있음을 보였다.
17 16
... ...